Pravesh Kothari
Constraint Satisfaction problems (CSPs) such as Max Cut and 3SAT, are one of the most basic computational problems but their complexity is not fully understood. For example, for most CSPs (i.e. when the predicate is chosen at random), while we have no algorithm that does better than simply outputting the random assignment, we also do not know if beating the approximation factor achieved by this simple algorithm is NP-hard. In this talk, we study algorithms based on linear and semidefinite programming for constraint satisfaction - techniques that are considered to be among the strongest generic tools in algorithm design - and show strong lower bounds ruling out algorithms based on linear programs ("linear extended formulations") and the sum of squares semidefinite programming hierarchy for beating the random assignment for a large class of CSPs.
Based on joint works with Boaz Barak, Siu On Chan, Raghu Meka and Prasad Raghavendra.